package com.kaili.utils;

import com.kaili.pojo.vo.StowageNodeVO;
import io.swagger.models.auth.In;

import java.math.BigDecimal;
import java.util.*;

/**
 * @Desc: 智能配载自定义方法
 * @author: renzhikun
 * @Time: 19-1-14 下午3:49
 * @Copyright: ©  杭州凯立通信有限公司 版权所有
 * @Warning: 本内容仅限于公司内部传阅, 禁止外泄或用于其它商业目的
 */
public class StowageUtil {

    /**
     * 递归装箱
     * @param i
     * @param v
     * @param w
     * @param set
     * @param tmp
     * @param list
     * @return
     */
    private static List<List<StowageNodeVO>> powerList(int i, double v, double w, List<StowageNodeVO> set, List<StowageNodeVO> tmp, List<List<StowageNodeVO>> list) {
        List<StowageNodeVO> setList = new ArrayList<>();
        if (i>set.size()){
            double m = 0;
            double n = 0;
            for (StowageNodeVO y : tmp) {
                m = y.getVol() + m;
                n = y.getWeight() + n;
            }
            if(m<v && n<w && !tmp.isEmpty()) {
                setList.addAll(tmp);
                list.add(setList);
//                tmp.forEach(p-> System.out.print(p +" "));
//                System.out.println();
            }
        }else {
            StowageNodeVO x = set.get(i-1);
            tmp.add(x);
            powerList(i+1, v,w, set, tmp, list);
            tmp.remove(x);
            powerList(i+1, v,w, set, tmp, list);
        }
        return list;
    }

    public static List<String> findMaxList(List<StowageNodeVO> set, double v,double w){
        List<StowageNodeVO> tmp = new ArrayList<>();
        List<List<StowageNodeVO>> list = new ArrayList<>();
        List<List<StowageNodeVO>> lists = powerList(1, v, w, set, tmp, list);
        if (lists.isEmpty()) {
            return null;
        }
//        lists.forEach(o -> System.out.println(o + "  "));
//        System.out.println(";");
        lists = maxVolSet(lists);
//        lists.forEach(o -> System.out.println(o + "  "));
//        System.out.println();
        lists = maxWeightSet(lists);
//        lists.forEach(o -> System.out.println(o + "  "));
        List<String> s = new ArrayList<>();
        for (List<StowageNodeVO> nodeVOList : lists) {
            for (StowageNodeVO nodeVO : nodeVOList) {
                s.add(nodeVO.getOperation());
            }
            break;
        }
        return s;
    }

    private static List<List<StowageNodeVO>> maxVolSet(List<List<StowageNodeVO>> set) {
        List<Double> sumList = new ArrayList<>();
        for (List<StowageNodeVO> s : set) {
           double sum = s.stream().mapToDouble(StowageNodeVO::getVol).sum();
           sumList.add(sum);
        }
        double max = Collections.max(sumList);
        set.removeIf(it -> it.stream().mapToDouble(StowageNodeVO::getVol).sum() != max);
        return set;
    }

    private static List<List<StowageNodeVO>> maxWeightSet(List<List<StowageNodeVO>> set) {
        List<Double> sumList = new ArrayList<>();
        for (List<StowageNodeVO> s : set) {
            double sum = s.stream().mapToDouble(StowageNodeVO::getWeight).sum();
            sumList.add(sum);
        }
        double max = Collections.max(sumList);
        set.removeIf(it -> it.stream().mapToDouble(StowageNodeVO::getWeight).sum() != max);
        return set;
    }

    /** @Desc:  lambda map 排序
     * @author: renzhikun
     * @Time: 19-1-16 上午10:11
     * @param map
     * @return java.util.Map<K,V>
     */
    private static <K, V extends Comparable<? super V>> Map<K,V> sortByValue(Map<K, V> map) {
        Map<K, V> sortMap = new LinkedHashMap<>();
        map.entrySet().stream().sorted((o1, o2) -> o2.getValue().compareTo(o1.getValue()))
                .forEach(entry -> sortMap.put(entry.getKey(), entry.getValue()));
        return sortMap;
    }

    /**
     * 动态规划装箱
     * @param W
     * @param wt
     * @param vl
     * @param n
     * @return
     */

    public static int[][] knapSack(int W, int wt[], int vl[], int n){
        int i, w;
        int K[][] = new int[n+1][W+1];
        for(i=1; i<=n; i++) {
            for (w=1; w<=W; w++){
                K[i][w] = K[i-1][w];
                if (wt[i-1] <= w && K[i][w] < K[i-1][w-wt[i-1]] + vl[i-1])
                    K[i][w] = K[i-1][w-wt[i-1]] + vl[i-1];
            }
        }
        return K;
    }

    /**
     * 二分查找矩阵比期望值小并且最接近期望值的下标
     * @param V
     * @param value
     * @param w
     * @param n
     */
    public static int[] binaryArray(int[][] V, int value, int n, int w) {
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Integer> kv = new HashMap<>();
        for(int i=0; i<w-1; i++){
            int result = binaryKey(V[i], value, n);
            map.put(i,V[i][result]);
            kv.put(i, result);
        }

        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort((o1, o2) -> (o2.getValue() - o1.getValue()));
        int l = list.get(0).getKey();
        int h = kv.get(l);
        return new int[]{l, h};
    }

    private static int binaryKey(int[] V, int value, int n) {
        int low = 0;
        int high = n;
        int target = 0;
        while (low <= high) {
            int mid = (int)Math.ceil((low + high)/2);
            if (V[mid] == value || (mid + 1) > n) {
                target =  mid;
                break;
            } else if (V[mid] < value) {
                if (V[mid+1] > value) {
                    target =  mid;
                    break;
                } else {
                    low = mid + 1;
                }
            } else {
                high = mid - 1;
            }
        }
        return target;
    }

    public static List<Integer> sackPrint(int wt[], int[][] V, int n, int[] t){
        List<Integer> list = new ArrayList<>();
        int[] x = new int[n];
        int k = t[1];
        for (int a=t[0]; a>=1; a--){
            if (V[a][k] > V[a-1][k]) {
                x[a-1] = 1;
                k = k - wt[a-1];
            }else {
                x[a-1] = 0;
            }
        }
        for (int b=0;b<n;b++){
            if (x[b]==1){
//                System.out.println(b+1);
                list.add(b);
            }
        }
        return list;
    }

    public static void main(String[] args){
        /*BigDecimal w = new BigDecimal("760000");
        BigDecimal v = new BigDecimal("990000");
        List<StowageNodeVO> stowageNodeVOS = new ArrayList<>();
        for (int i=1;i<=5;i++) {
            StowageNodeVO stowageNodeVO = new StowageNodeVO();
            stowageNodeVO.setOperation(String.valueOf(i));
            stowageNodeVO.setVol(20.00+i);
            stowageNodeVO.setWeight(20.00+i);
            stowageNodeVOS.add(stowageNodeVO);
        }
        for (int i=6;i<=10;i++) {
            StowageNodeVO stowageNodeVO = new StowageNodeVO();
            stowageNodeVO.setOperation(String.valueOf(i));
            stowageNodeVO.setVol(30.0+i);
            stowageNodeVO.setWeight(30.0+i);
            stowageNodeVOS.add(stowageNodeVO);
        }
        findMaxList(stowageNodeVOS, v.doubleValue(),w.doubleValue());*/
        int vl[] = {200, 250, 140, 150};
        int wt[] = {1, 3, 2, 5};
        int W = 5;
        int n = vl.length;
        int value = 350;
        int[][] k = knapSack(W, wt, vl, n);
        int[] t = binaryArray(k, value, W, n);
        List<Integer> list = sackPrint(wt, k, n, t);

    }

}
